/*
 * @lc app=leetcode.cn id=297 lang=javascript
 *
 * [297] 二叉树的序列化与反序列化
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
// 广度优先遍历
var serialize = function(root) {
  const queue = [root]
  const res = []
  while (queue.length) {
    const list = [...queue]
    queue.length = 0
    for (let i = 0; i < list.length; i++) {
      let item = list[i]
      if (item) {
        res.push(item.val)
        queue.push(item.left)
        queue.push(item.right)
      } else {
        res.push('null')
      }
    }
  }
  return res.join(',')
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
// 用队列依次先进先出，从上到下，从左到右填充节点
var deserialize = function(data) {
  if (data === 'null') return null;
  const list = data.split(',')
  const root = new TreeNode(list.shift())
  const queue = [root]
  while (queue.length) {
    const current = queue.shift()
    const [l, r] = list.splice(0, 2)
    if (l !== 'null') {
      current.left = new TreeNode(l)
      queue.push(current.left)
    }
    if (r !== 'null') {
      current.right = new TreeNode(r)
      queue.push(current.right)
    }     
  }
  return root
};
/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */
// @lc code=end

